#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 有效的括号
// 最小栈
// 字符串解码
// 每日温度
// 数据流的中位数
// 最长有效括号

// 有效的括号
class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto x : s)
        {
            if (x == ')')
            {
                if (st.empty() || st.top() != '(')
                    return false;
                st.pop();
            }
            else if (x == '}')
            {
                if (st.empty() || st.top() != '{')
                    return false;
                st.pop();
            }
            else if (x == ']')
            {
                if (st.empty() || st.top() != '[')
                    return false;
                st.pop();
            }
            else
                st.push(x);
        }

        return st.empty();
    }
};


// 最小栈
class MinStack
{
private:
    stack<int> st;
    stack<int> min_st;

public:
    MinStack()
    {
    }

    void push(int val)
    {
        st.push(val);
        if (min_st.empty() || val <= min_st.top())
            min_st.push(val);
        else
            min_st.push(min_st.top());
    }

    void pop()
    {
        st.pop();
        min_st.pop();
    }

    int top()
    {
        return st.top();
    }

    int getMin()
    {
        return min_st.top();
    }
};


// 字符串解码
class Solution
{
public:
    string decodeString(string s)
    {
        stack<int> num;
        stack<string> st;
        st.push("");
        int i = 0, n = s.size();
        while (i < n)
        {
            // 遇到数字,提取数字,放入数字栈中
            if (s[i] >= '0' && s[i] <= '9')
            {
                int cnt = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                {
                    cnt = cnt * 10 + s[i] - '0';
                    i++;
                }
                num.push(cnt);
            }
            // 遇到左括号,把后面的字符串提取出来,放入字符串栈中
            else if (s[i] == '[')
            {
                i++;
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp);
            }
            // 遇到右括号,解析，放到字符串栈栈顶的字符串的后面
            else if (s[i] == ']')
            {
                int cnt = num.top();
                num.pop();
                string str = st.top();
                st.pop();
                string tmp;
                while (cnt--)
                {
                    tmp += str;
                }
                st.top() += tmp;
                i++;
            }
            // 普通字符串，放到字符串栈栈顶的字符串的后面
            else
            {
                st.top() += s[i];
                i++;
            }
        }

        return st.top();
    }
};


// 每日温度
class Solution
{
public:
    vector<int> dailyTemperatures(vector<int> &temperatures)
    {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> st;
        for (int i = 0; i < n; i++)
        {
            // 右边比栈顶小就入栈,大就更新，一直和栈顶进行比较
            while (!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                int preindex = st.top();
                ans[preindex] = i - preindex;
                st.pop();
            }
            st.push(i);
        }

        return ans;
    }
};


// 数据流的中位数
class MedianFinder
{
private:
    // 小根堆里存大数,大根堆里存小的数
    // 偶数个分别取堆头除以2,奇数取小根堆堆头元素
    priority_queue<int> min_heap;                            // 大堆存小的数
    priority_queue<int, vector<int>, greater<int>> max_heap; // 小堆存大的数
public:
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        if (min_heap.empty() || num <= min_heap.top())
        {
            min_heap.push(num);
            if (min_heap.size() > max_heap.size() + 1)
            {
                max_heap.push(min_heap.top());
                min_heap.pop();
            }
        }
        else
        {
            max_heap.push(num);
            if (max_heap.size() > min_heap.size())
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
        }
    }

    double findMedian()
    {
        if (min_heap.size() > max_heap.size())
        {
            return min_heap.top();
        }
        return (min_heap.top() + max_heap.top()) / 2.0;
    }
};


// 最长有效括号
class Solution
{
public:
    int longestValidParentheses(string s)
    {
        // 保持栈底元素为最后一个没有匹配的右括号的下标
        stack<int> st;
        st.push(-1);
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(')
            {
                st.push(i);
            }
            else
            {
                // 弹出栈顶元素表示匹配了当前有括号
                st.pop();
                // 如果栈为空,则说明当前的有括号为没有被匹配的右括号
                // 将其下标入栈作为最后一个没有被匹配的右括号的下标
                if (st.empty())
                {
                    st.push(i);
                }
                // 如果栈不为空,当前右括号下标减去栈顶元素
                ans = max(ans, i - st.top());
            }
        }

        return ans;
    }
};
